#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <limits.h>

#define INF INT_MAX
#define LEN 5

void dijkstra(int start, int end, int n, int *dist, int *prev, int **graph) {
    // vistited数组是记录是否已经访问的数组
    bool *visited = (bool*)malloc(n * sizeof(bool));
    memset(visited, false, n * sizeof(bool));
    // 首先把初值赋值，这是Cursor给我生成的代码，我们就以这个为例
    // 赋值完成以后，结果是这样：
    // dist: 0 10 INF 30 100
    // prev: 0 0  -1  0  0
    // visited: false false false false false
    for (int i = 0; i < n; i++) {
        dist[i] = graph[start][i];
        if (dist[i] == INF) {
            prev[i] = -1;
        } else {
            prev[i] = start;
        }
    }
    visited[start] = true;
    for (int i = 1; i < n; i++) {
        int min_dist = INF;
        int u = -1;
        // 选择每个顶点的最近顶点
        // i = 1时，min_dist = 10，u = 1
        // i = 2时，min_dist = 30，u = 3
        // i = 3时，min_dist = 50, u = 2
        // i = 4时，min_dist = 60, u = 4
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                u = j;
            }
        }
        if (u == -1) {
            break;
        }
        visited[u] = true;
        for (int v = 0; v < n; v++) {
            if (visited[v])
            {
                continue;
            }
            if (graph[u][v] == INF) 
            {
                continue;
            }
            if (dist[u] + graph[u][v] > dist[v]) 
            {
                continue;
            }
            dist[v] = dist[u] + graph[u][v];
            prev[v] = u;
        }
    }
    // 第一遍运行完毕后，dist是：0 10 60 30 100
    //                  prev是：0 0  1  0  0
    //                  visited是：true true  false  false  false
    // 第二遍运行完毕后，dist是：0 10 50 30 90
    //                  prev是：0 0  3  0  3
    //                  visited是：true true  false  true  false
    // 第三遍运行完毕后，dist是：0 10 50 30 60 
    //                  prev是：0 0  3  0  2 
    //                  visited是：true true  true  true  false
    // 第四遍运行完毕后，dist是：0 10 50 30 60
    //                  prev是：0 0  3  0  2 
    //                  visited是：true true  true  true  true
    free(visited);
}


int main() {
    int start = 0;
    int end = 4;
    int dist[LEN];
    int prev[LEN];
    int graph[LEN][LEN] = {
        {0, 10, INF, 30, 100},
        {INF, 0, 50, INF, INF},
        {INF, INF, 0, INF, 10},
        {INF, INF, 20, 0, 60},
        {INF, INF, INF, INF, 0}    

    };
    // 这个地方比较坑，一定要记得这次教训，不能直接将graph传到dijkstra，不然会导致段错误。
    // 这里涉及到c语言的底层逻辑，二维数组和指向指针的指针不是完全一样的，如果我们把二维数组当成指向指针的指针传到函数里，就会导致在
    // 访问的时把二维数组的前两个元素（或者1位元素，具体看操作系统位数）当成一个指针地址去访问，这样就会导致段错误，这是一个比较深刻的教训
    int *g[LEN];
    for (int i = 0; i < LEN; i++) {
        g[i] = (int*)malloc(LEN * sizeof(int));
        memcpy(g[i], graph[i], LEN * sizeof(int));
    }
    dijkstra(start, end, LEN, dist, prev, (int**)g);
    printf("Shortest distance from %d to %d is %d\n", start, end, dist[end]);
    return 0;
}

